import lombok.Data;

import java.util.concurrent.ArrayBlockingQueue;

/**
 * TODO 二叉树操作，有bug待解决
 *
 * @param <T>
 */
@Data
public class 二叉树操作<T> {

    private Binary<T> binary;
    private Integer length;
    private T[] ts;

    public 二叉树操作<T> initBinary(T[] ts) {
        if (ts == null || ts.length <= 0) {
            throw new IllegalStateException("array must not be empty");
        }
        this.setBinary(new Binary<T>(ts[0], 0));
        this.setLength(ts.length);
        this.setTs(ts);

        ArrayBlockingQueue<Binary<T>> queue = new ArrayBlockingQueue<>(this.getTs().length);
        queue.add(this.getBinary());
        while (!queue.isEmpty()) {
            Binary<T> binary = queue.poll();
            Integer idx = binary.getIndex();
            Integer leftCh = idx * 2 + 1;
            Integer rightCh = idx * 2 + 2;
            if (leftCh < this.getLength() && ts[leftCh] != null) {
                Binary<T> tBinary = new Binary<>(ts[leftCh], leftCh);
                binary.setLeft(tBinary);
                queue.add(tBinary);
            }
            if (rightCh < this.getLength() && ts[rightCh] != null) {
                Binary<T> tBinary = new Binary<>(ts[rightCh], rightCh);
                binary.setRight(tBinary);
                queue.add(tBinary);
            }
        }
        return this;
    }

    public void revertBinary() {
        ArrayBlockingQueue<Binary<T>> queue = new ArrayBlockingQueue<>(this.getTs().length);
        queue.add(this.getBinary());
        while (!queue.isEmpty()) {
            Binary binary = queue.poll();
            if (binary.getLeft() != null && binary.getRight() != null) {
                Binary temp = binary.getLeft();
                Integer tempIdx = temp.getIndex();
                temp.setIndex(binary.getRight().getIndex());
                Binary right = binary.getRight();
                right.setIndex(tempIdx);
                binary.setLeft(right);
                binary.setRight(temp);
                binary.getLeft().setIndex(binary.getIndex() * 2 + 1);
                binary.getRight().setIndex(binary.getIndex() * 2 + 2);
                queue.add(binary.getLeft());
                queue.add(binary.getRight());
            } else {
                if (binary.getLeft() != null) {
                    binary.getLeft().setIndex(binary.getIndex() * 2 + 1);
                    queue.add(binary.getLeft());
                }
                if (binary.getRight() != null) {
                    binary.getRight().setIndex(binary.getIndex() * 2 + 2);
                    queue.add(binary.getRight());
                }
            }
        }
    }

    public T[] getArr() {
        ArrayBlockingQueue<Binary<T>> queue = new ArrayBlockingQueue<>(this.getTs().length);
        queue.add(this.getBinary());
        T[] ts = this.getTs();
        while (!queue.isEmpty()) {
            Binary<T> binary = queue.poll();
            ts[binary.getIndex()] = binary.getValue();
            if (binary.getLeft() != null) {
                queue.add(binary.getLeft());
            }
            if (binary.getRight() != null) {
                queue.add(binary.getRight());
            }
        }
        return ts;
    }

    @Data
    public static class Binary<T> {
        private T value;
        private Integer index;
        private Binary left;
        private Binary right;

        public Binary(T value, Integer index, Binary left, Binary right) {
            this.value = value;
            this.index = index;
            this.left = left;
            this.right = right;
        }

        public Binary(T value, Integer index) {
            this.value = value;
            this.index = index;
        }
    }

    public static void main(String[] args) {
        二叉树操作<Integer> bit = new 二叉树操作<>();
        bit.initBinary(new Integer[]{1,
                2, 3,
                4, 5, 6, 7,
                8, 9, 10, 11, 12, 13, 14, 15});
        Integer length = bit.getLength();
        int h = 0;
        int x = 1;
        while (x > 0) {
            x = (length - 1) / 2;
            length = x;
            h++;
        }
//        System.out.println(h);
//        for (Integer is : bit.getArr()) {
//            System.out.print(is + ",");
//        }
//        System.out.println();
        bit.revertBinary();
        Integer[] arr = bit.getArr();
        int l = 0;
        int c = 1;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
            if (c++ >= (int) (Math.pow(2, l) + 1) / 2 * (l + 1)) {
                System.out.println();
                l++;
            }
        }
    }
}
